package com.xuyuan.arithmetic.datastructure.quest;

import org.junit.jupiter.api.Test;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 链表常见场景算法
 *
 * @author xuyuan
 */
public class LinkedNodeSolution {

    /**
     * @desc 两数相加
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * 2->4->3 + 5->6->4 = 7->0->8
     */
    ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

    /**
     * @desc 合并两个升序链表
     * 合并链表升序排列。
     * 1->2->4 + 1->3->4 = 1->1->2->3->4->4
     */
    ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 != null ? l1 : l2;
        }
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }

    /**
     * @desc 合并 k个升序链表
     * 合并 k个链表
     */
    ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        if (l > r) {
            return null;
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    /**
     * 删除链表中的第k个节点
     * 栈解决
     */
    ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<ListNode>();
        // Stack<ListNode> stack = new Stack();
        ListNode cur = dummy;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

    /**
     * @desc 删除链表中的第k个节点
     * 双指针解决
     */
    ListNode removeNthFromEnd1(ListNode head, int n) {
        // 新建一个虚拟头节点指向head
        ListNode dummyNode = new ListNode(0, head);
        // 快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            fastIndex = fastIndex.next;
        }
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }

    /**
     * 两两交换链表中的节点
     * 1->2->3->4->5->6->7->8, 返回 2->1->4->3->6->5->8->7
     */
    ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = dummy;
        while (current.next != null && current.next.next != null) {
            ListNode first = current.next;
            ListNode second = current.next.next;
            first.next = second.next;
            second.next = first;
            current.next = second;
            current = first;
        }
        return dummy.next;
    }

    /**
     * 旋转链表
     * 链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。
     * 临界点的指针需要调整，尾节点一定指向头节点，临界点的指针为null；
     */
    ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k <= 0) {
            return head;
        }
        ListNode end = head;
        int length = 1;
        while (end.next != null) {
            end = end.next;
            length++;
        }
        k = k % length;
        if (k == 0) return head;
        ListNode result = null;
        ListNode dummy = head;
        for (int i = 0; i < length; ) {
            if (++i == length - k) {
                result = dummy.next;
                dummy.next = null;
                break;
            }
            dummy = dummy.next;
        }
        end.next = head;
        return result;
    }


    /**
     * 反转链表
     * 1->2->3->4->5->NULL, 返回 5->4->3->2->1->NULL
     */
    ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * k个一组翻转链表
     */
    ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null || k <= 1) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;
        while (end.next != null) {
            end = end.next;
            int length = 0;
            while (length < k && end != null) {
                end = end.next;
                length++;
            }
            if (length == k) {
                ListNode start = pre.next;
                ListNode next = end.next;
                end.next = null;
                pre.next = reverseList(start);
                start.next = next;
                pre = start;
            }
        }
        return dummy.next;
    }

    /**
     * @desc 删除链表中等于给定值 val 的所有节点。
     */
    ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head);
        ListNode temp = dummy;
        while (temp.next != null) {
            ListNode next = temp.next;
            if (next.val == val) {
                temp.next = next.next;
            } else {
                temp = next;
            }
        }
        return dummy.next;
    }

    /**
     * @desc 反转链表II
     * 反转链表的left - right范围内的元素
     * 1->2->3->4->5->NULL, left = 2, right = 4, 返回 1->4->3->2->5->NULL
     * left<right
     */
    ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummy.next;
    }

    public ListNode buildList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    @Test
    public void test() {
        LinkedNodeSolution solution = new LinkedNodeSolution();
        int[] values = {1, 2, 3, 4, 5};
        ListNode head = solution.buildList(values);
        ListNode listNode = reverseBetween(head, 2, 4);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}